home *** CD-ROM | disk | FTP | other *** search
/ MACD 5 / MACD 5.bin / workbench / libs / toollib.lha / ToolLib / Source / qsort.s < prev    next >
Text File  |  1991-04-17  |  4KB  |  106 lines
  1.             opt     l+,o+,ow-
  2. *
  3. *   qsort.s version 8.1 - © Copyright 1990 Jaba Development
  4. *
  5. *   Author    : Jan van den Baard
  6. *   Assembler : Devpac vesion 2.14
  7. *
  8.             incdir  'sys:devpac_inc/'
  9.             include 'mymacros.i'
  10.  
  11.             xdef    SwapMem
  12.             xdef    QuickSort
  13.  
  14. *
  15. * QuickSort(base,num,size,compar)
  16. *            a0   d0  d1   a1
  17. *
  18. QuickSort:  move.l  a1,-(sp)
  19.             movem.l d0-d1,-(sp)
  20.             move.l  a0,-(sp)
  21.             bsr.s   QSort
  22.             lea.l   16(sp),sp
  23.             rts
  24. *
  25. * sort an array of elements.
  26. * this routine is recursive it needs a lot of stack when sorting
  27. * a large number of elements!
  28. * the elements in the array may NOT be bigger than 64 KByte!
  29. *
  30. QSort:      movem.l d2-d5/a2-a3,-(sp)
  31.             move.l  28(sp),a2               ; array base
  32.             move.l  32(sp),d2               ; number of elements
  33.             move.l  36(sp),d3               ; size of a element
  34.             move.l  40(sp),a3               ; comparrison routine
  35.             tst.l   d2                      ; sort if there are elements
  36.             bne.s   SortIt
  37. EndQS:      movem.l (sp)+,d2-d5/a2-a3
  38.             rts
  39. SortIt:     cldat   d4                      ; offset = 0
  40.             moveq   #1,d5                   ; n = 1
  41.             bra.s   ChkEnd                  ; check if all are done
  42. CmpLoop:    move.l  a2,-(sp)                ; base[0] = x
  43.             move.l  a2,a1
  44.             move.l  d3,d0
  45.             mulu    d5,d0
  46.             add.l   a2,d0
  47.             move.l  d0,-(sp)
  48.             move.l  d0,a0
  49.             jsr     (a3)                    ; cmp(base+(n*size),x);
  50.             addq.w  #8,sp
  51.             tst.l   d0
  52.             bge.s   NoSwap                  ; if result >= 0 then dont swap
  53.             inc.l   d4                      ; offset++
  54.             move.l  d3,d1                   ; size
  55.             move.l  a2,a0
  56.             move.l  d3,d0
  57.             mulu    d5,d0
  58.             add.l   d0,a0                   ; base + (n*size)
  59.             move.l  a2,a1
  60.             move.l  d3,d0
  61.             mulu    d4,d0
  62.             add.l   d0,a1                   ; base + (offset*size)
  63.             bsr.s   SwapMem                 ; SwapMem()
  64. NoSwap:     inc.l   d5                      ; n++
  65. ChkEnd:     cmp.l   d2,d5                   ; n < num ?
  66.             bcs.s   CmpLoop                 ; if so.. loop
  67.             move.l  d3,d1                   ; size
  68.             move.l  a2,a0                   ; base
  69.             move.l  a2,a1
  70.             move.l  d3,d0
  71.             mulu    d4,d0
  72.             add.l   d0,a1                   ; base + (offset*size)
  73.             bsr.s   SwapMem                 ; SwapMem()
  74.             move.l  a3,-(sp)                ; cmp()
  75.             move.l  d3,-(sp)                ; size
  76.             move.l  d4,-(sp)                ; offset
  77.             move.l  a2,-(sp)                ; base
  78.             bsr.s   QSort                   ; QSort()
  79.             addq.w  #8,sp
  80.             move.l  d2,d0
  81.             sub.l   d4,d0
  82.             dec.l   d0
  83.             move.l  d0,-(sp)                ; num - offset - 1
  84.             move.l  d3,d0
  85.             mulu    d4,d0
  86.             add.l   d3,d0
  87.             add.l   a2,d0
  88.             move.l  d0,-(sp)                ; base + (offset*size) + size
  89.             bsr     QSort                   ; QSort
  90.             lea.l   16(sp),sp
  91.             bra.s   EndQS
  92.  
  93. *
  94. * SwapMem(mema,memb,size)
  95. *          a0   a1   d1
  96. * this routine does NOT swap memory chunks bigger than 64 Kbyte! (should be
  97. * enough)
  98. *
  99. SwapMem:    bra.s   ChkDone
  100. Swap:       move.b  (a0),d0                 ; byte = *area1
  101.             move.b  (a1),(a0)+              ; *area1++ = *area2
  102.             move.b  d0,(a1)+                ; *area2++ = byte
  103. ChkDone:    dbra    d1,Swap                 ; loop until 'size' bytes done
  104.             rts
  105.  
  106.